二分搜尋有隨機訪問的特性，在數組是有序的情況下，透過訪問的元素，推測左右兩側的性質，展現較高的效率。
以下整理己主以下整理幾種解題時會出現的模板

模板

標準的二分搜尋

//標準的二分搜尋
int find_target(const int& target, const vector<int>& arr){
    int f = 0;
    int b = arr.size()-1;
    while(b>=f){
        int mid = (b+f)/2; //中點
        if(arr[mid]==target){
            return mid;
        }
        if(arr[mid]>target){    //目前的mid>target，要尋找的值應該在左側
            b = mid-1;  //已經確定mid不是target, 可以從mid-1移動b
        }
        if(arr[mid]<target){    //要尋找的值應該在右側
            f = mid+1;  //已經確定mid不是target, 可以從mid+1移動f
        }
    }
    return -1;  //not found
}

如果沒有搜尋到，兩個指針的情形

//應對沒有搜尋到目標，返回比目標大的值其索引

int find_target_return_f(const int& target, const vector<int>& arr){
    int f = 0;
    int b = arr.size()-1;
    while(b>=f){
        int mid = (b+f)/2; 
        if(arr[mid]==target){
            return mid;
        }
        if(arr[mid]>target){
            b = mid-1; 
        }
        if(arr[mid]<target){
            f = mid+1;
        }
    }
    return f;   //not found
    //return b;  // -->返回比目標小的值其索引
}

另一種寫法

//返回較大索引的另一種寫法
int find_target_return_bigger(const int& target, const vector<int>& arr){
    int f = 0;
    int b = arr.size()-1;
    while(b>f){ //這邊要改寫成沒有等號，以免會無限循環(b==f時)
        int mid = (b+f)/2;  //中點
        if(arr[mid]==target){
            return mid;
        }
        if(arr[mid]>target){ //因目的是返回比目標大的最小索引，此處mid可能是答案，保留，尋找更小的索引
            b = mid;
        }
        if(arr[mid]<target){
            f = mid+1; //若小於target不符合規定，f不可能是答案，直接移動至mid+1
        }
    }
    return b;
}

有了模板之後就可以開始刷題了

例題實戰

1482. 制作 m 束花所需的最少天数
編寫achievable檢查後，以二分搜尋法帶入
((暴力法一一帶入；速度太慢))

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
    //[暴力法]超時
        // vector<int> hash = bloomDay;
        // sort(hash.begin(), hash.end());
        // int res = -1;
        // for(int i = 0; i<hash.size(); i++){
        //     res = hash[i];
        //     int cnt = 0;
        //     int contin = 0;
        //     for(int j = 0; j<bloomDay.size(); j++){
        //         if(bloomDay[j]<=res){
        //             contin++;
        //             if(contin==k){
        //                 cnt++;
        //                 contin = 0;
        //             }
        //         }
        //         else{
        //             contin = 0;
        //         }
        //         if(cnt==m){
        //             return res;
        //         }
        //     }
        // }
        // return -1;
    //[二分搜尋法]優化通過
        int mmax = -1;
        for(int i = 0; i<bloomDay.size(); i++){
            mmax = max(bloomDay[i], mmax);
        }
        int res = -1;
        int b = mmax;
        int f = 0;
        while(b>=f){
            int mid = (f+b)/2;
            if(achievable(bloomDay, m, k, mid)){
                res = mid;
                b = mid-1;
            }
            else{
                f = mid+1;
            }
        }
        return res;
    }
    bool achievable(vector<int>& bloomDay, int m, int k, int day){
        int cnt = 0;
        int contin = 0;
        for(int i = 0; i<bloomDay.size(); i++){
            if(bloomDay[i]<=day){
                contin++;

-----


                if(contin==k){
                    cnt++;
                    contin = 0;
                }
            }
            else{
                contin = 0;
            }
            if(cnt==m){
                return true;
            }
        }
        return false;
    }

};

這題之前有放過了，再提一次==刷了兩次還是會沒想法
162. 寻找峰值

if nums[mid]>nums[mid+1] 則 [mid+1 ~ N]必有峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int f = 0;
        int b = nums.size()-1;
        int mid = -1;
        while(b>f){
            mid = (f+b)/2;
            if(nums[mid]>nums[mid+1]){
                b = mid;
            }
            else{
                f = mid+1;
            }
        }
        return f; 
    }
};